home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_09_01
/
9n01070a
< prev
next >
Wrap
Text File
|
1990-11-18
|
18KB
|
750 lines
// TREE.CPP - implementation of balanced binary trees.
#include <stream.hpp>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "tree.hpp"
// constants which tell which way the subtree is out of balance
#define BALANCED 0
#define LEFT -1
#define RIGHT 1
#define DOUBLE_LEFT (LEFT*2)
#define DOUBLE_RIGHT (RIGHT*2)
#define RETURN_CURRENT 0 // messages used by getprev() and getnext()
#define RETURN_PARENT 1
// maximum allowable imbalance in a subtree
#define ALLOWABLE_IMBALANCE 1
// messages passed from a child to a parent node
#define DELETE_THIS_NODE 2
#define TREE_SHRANK 1
#define NO_CHANGE 0
#define NODE_NOT_FOUND -2
TREE::TREE(void) // construct a tree
{
head = NULL;
current = NULL;
errval = OK;
}
void TREE::delete_subtree(NODE *nodeptr)
{
if(nodeptr->right != NULL)
{
delete_subtree(nodeptr->right);
delete nodeptr->right;
}
if(nodeptr->left != NULL)
{
delete_subtree(nodeptr->left);
delete nodeptr->left;
}
delete_data(nodeptr);
}
TREE::~TREE(void) // destroy a tree
{
if(head != NULL)
{
delete_subtree(head);
delete head;
head = NULL;
}
}
void TREE::rebalance(NODE *parent)
{
NODE *p1, *p2;
NODE swapnode;
if(parent->balance == DOUBLE_LEFT)
{
if(parent->left->balance != RIGHT) // LL imbalance
{
p1 = parent->left;
parent->left = p1->right;
p1->right = p1; // will resolve properly after node swapping
if(p1->balance == LEFT)
parent->balance = p1->balance = BALANCED;
else
{
parent->balance = LEFT;
p1->balance = RIGHT;
}
swapnode = *parent;
*parent = *p1;
*p1 = swapnode;
}
else // LR imbalance
{
p1 = parent->left;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
parent->left = p2->right;
p2->right = p2; // will resolve properly after node swapping
if(p2->balance == RIGHT)
{
parent->balance = BALANCED;
p1->balance = LEFT;
p2->balance = RIGHT;
}
else if(p2->balance == LEFT)
{
parent->balance = RIGHT;
p1->balance = BALANCED;
p2->balance = BALANCED;
}
else
parent->balance = p1->balance = p2->balance = BALANCED;
swapnode = *parent;
*parent = *p2;
*p2 = swapnode;
}
}
else // parent->balance == DOUBLE_RIGHT
{
if(parent->right->balance != LEFT) // RR imbalance
{
p1 = parent->right;
parent->right = p1->left;
p1->left = p1; // will resolve properly after node swapping
if(p1->balance == RIGHT)
parent->balance = p1->balance = BALANCED;
else
{
parent->balance = RIGHT;
p1->balance = LEFT;
}
swapnode = *parent;
*parent = *p1;
*p1 = swapnode;
}
else // RL imbalance
{
p1 = parent->right;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
parent->right = p2->left;
p2->left = p2; // will resolve properly after node swapping
if(p2->balance == RIGHT)
{
parent->balance = LEFT;
p1->balance = BALANCED;
p2->balance = BALANCED;
}
else if(p2->balance == LEFT)
{
parent->balance = BALANCED;
p1->balance = RIGHT;
p2->balance = BALANCED;
}
else
parent->balance = p1->balance = p2->balance = BALANCED;
swapnode = *parent;
*parent = *p2;
*p2 = swapnode;
}
}
}
int TREE::addnode(NODE *parent, NODE *newnode)
{
int retval;
int addside;
if((retval = compare(parent->data,newnode->data,parent->dsize)) != 0)
{
if(retval < 0) // parent < newnode - add on RIGHT side of parent
{
if(parent->right != NULL)
retval = addnode(parent->right,newnode);
else
{
parent->right = newnode;
retval = (parent->balance == LEFT) ? 0 : 1;
}
addside = RIGHT;
}
else // parent > newnode - add on LEFT side of parent
{
if(parent->left != NULL)
retval = addnode(parent->left,newnode);
else
{
parent->left = newnode;
retval = (parent->balance == RIGHT) ? 0 : 1;
}
addside = LEFT;
}
}
else // duplicate items not allowed
{
errval = NO_DUPES;
return 0;
}
// Part B - adjust the parent balance if necessary
if(retval != 0) // tree changed depth
{
parent->balance += addside;
if(abs(parent->balance) > ALLOWABLE_IMBALANCE)
rebalance(parent);
}
return (parent->balance == BALANCED) ? 0 : retval;
}
int TREE::add(void *data, size_t size)
{
// build the node to be added
errval = OK;
NODE *nptr = new NODE;
if(nptr == NULL) // unable to allocate new node
{
errval = MEM_ALLOC_FAIL;
return 0;
}
nptr->left = NULL;
nptr->right = NULL;
nptr->balance = BALANCED;
nptr->dsize = size;
alloc_data(nptr);
if(errval != OK)
return 0;
copy_data(nptr, data);
// Now determine where to add the new node
if(head == NULL)
head = nptr;
else
addnode(head, nptr);
if(errval == OK)
return 1;
else
return 0;
}
static NODE *walk_tree(NODE *nptr, int walk_side)
{
if(walk_side == RIGHT)
{
if(nptr->right == NULL)
return nptr;
else
return walk_tree(nptr->right, walk_side);
}
else // walk_side == LEFT
{
if(nptr->left == NULL)
return nptr;
else
return walk_tree(nptr->left, walk_side);
}
}
int TREE::remove_node(NODE *currnode, void *key)
{
int retval,crval,remove_side;
NODE *new_head_ptr;
NODE worknode;
if((crval = compare(currnode->data,key,currnode->dsize)) < 0)
{
if(currnode->right != NULL)
{
remove_side = RIGHT;
retval = remove_node(currnode->right, key);
}
else
return NODE_NOT_FOUND;
}
else if(crval > 0)
{
if(currnode->left != NULL)
{
remove_side = LEFT;
retval = remove_node(currnode->left, key);
}
else
return NODE_NOT_FOUND;
}
else // currnode is the node to remove
{
if(currnode->left == NULL && currnode->right == NULL) // no descendants
return DELETE_THIS_NODE;
else if( (currnode->left == NULL && currnode->right != NULL) ||
(currnode->left != NULL && currnode->right == NULL))
{ // one descendant
NODE *saveptr;
if(currnode->left != NULL)
{
saveptr = currnode->left;
*currnode = *(currnode->left);
delete saveptr;
}
else
{
saveptr = currnode->right;
*currnode = *(currnode->right);
delete saveptr;
}
return TREE_SHRANK;
}
else // two descendants
{
if(currnode->balance == LEFT)